package org.tonny.algorithm.leetcode;

import java.util.PriorityQueue;

/**
 * 23. 合并K个升序链表
 */
public class LeetCode23 {
    public ListNode mergeKLists(ListNode[] lists) {
        // 优先级队列，小顶堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> (a.val - b.val));
        //插入所有链表的数据
        for (int i = 0; i < lists.length; i++) {
            ListNode head = lists[i];
            while (head != null) {
                queue.offer(head);
                head = head.next;
            }
        }

        //取出堆数据，转换为链表
        ListNode tmp = new ListNode();
        ListNode ptr = tmp;
        while (!queue.isEmpty()) {
            ptr.next = queue.poll();
            ptr = ptr.next;
        }
        ptr.next = null;
        return tmp.next;
    }
}
